package com.lingyi.algorithm.lab5;

import cn.hutool.json.JSON;
import cn.hutool.json.JSONUtil;

/**
 * kmp算法
 * @author chenweilong
 * @email 1433471850@qq.com
 * @date 2020-08-21 14:02
 */
public class KMPMatch {

    public static void main(String[] args) {

        int sub = 0;

//        KMPMatch.getNext("abaabe");


        String mString = "defdeldemdesddmdes";

        String subString  = "des";
        //获取next数组
        int[] next = getNext(subString);

        System.out.println(JSONUtil.toJsonStr(next));

        char[] mChars = mString.toCharArray();
        char[] subChars = subString.toCharArray();



        int m = 0;
        int s = 0;



        while (m < mChars.length && s < subChars.length) {
            sub++;
            if (mChars[m] == subChars[s]) {
                m++;
                s++;
            }else {
                s = next[s + 1];

                if (s == 0) {
                    m++;
                }else if (s == 1) {
                    s = 0;
                }

            }
        }

        System.out.printf("一共运行的次数%s\n",sub);

        if (s == subChars.length) {
            System.out.println(m - s);
        }else {
            System.out.println(-1);
        }



    }



    public static int[] getNext(String subString) {
        char[] chars = subString.toCharArray();
        int[] arr = new int[chars.length + 5];

        int j = 1,k = 0;
        arr[j] = k;
        while (j < chars.length) {
            if (k == 0 || chars[j - 1] == chars[k -1]) {
                arr[++j] = ++k;
            }else {
                k = arr[k];
            }
        }

        return arr;
    }



}
